package algotithm.leetcode.dp.hot.test494;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/12-21:44
 * @URL https://leetcode-cn.com/problems/target-sum/
 * @Title 494. 目标和
 */
public class Solution {

    public static void main(String[] args) {
        int[] nums = {1,1,1,1,1};
        int S = 3;
        Solution solution = new Solution();
        int targetSumWays = solution.findTargetSumWays(nums, S);
        System.out.println(targetSumWays);
    }

    public int findTargetSumWays(int[] nums,int S) {
        int[] dp = new int[2001];
        dp[1000 - nums[0]] = 1;
        dp[1000 + nums[0]] += 1;
        for (int i = 1; i < nums.length; i++) {
            int[] next = new int[2001];
            for (int j = -1000; j <= 1000; j++) {
                if (dp[j + 1000] > 0) {
                    next[j + nums[i] + 1000] += dp[j + 1000];
                    next[j - nums[i] + 1000] += dp[j + 1000];
                }
            }
            dp = next;
        }
        return S > 1000 ? 0 : dp[S + 1000];
    }

}
